package com.gitee.wsl.lang

import com.gitee.wsl.ext.bitcode.countLeadingZeros


/**
 *
 *
 * This class provides a compact integer array for applications where integers
 * are stored for which the width is known beforehand and that are not (necessarily)
 * 8, 16, or 32 bits wide.
 *
 *
 *
 * [.get] and [.set] are in O(1) time.
 *
 */
class CompactIntArray(
    private val d_size: Int,
    private val d_bitsPerElem: Int
) {
    private val d_data: IntArray

    /**
     * Construct an array of the given number of elements and (maximum) bit width per element.
     *
     * @param d_size      The number of elements.
     * @param d_bitsPerElem The number of bits per element.
     */
    init {
        var arrSize = (d_size * d_bitsPerElem) / INT_SIZE
        if ((d_size * d_bitsPerElem) % INT_SIZE != 0) ++arrSize

        d_data = IntArray(arrSize)
    }

    /**
     * Search a value in the array, the subarray *(fromIndex, toIndex]* should be sorted.
     * @param fromIndex The index of the first element to be searched.
     * @param toIndex The index of the last element to be searched (exclusive).
     * @param value The value to be searched.
     * @return
     */
    fun binarySearch(fromIndex: Int, toIndex: Int, value: Int): Int {
        var fromIndex = fromIndex
        var toIndex = toIndex
        --toIndex

        while (toIndex >= fromIndex) {
            val mid = (fromIndex + toIndex) ushr 1
            val midVal = get(mid)

            if (midVal > value) toIndex = mid - 1
            else if (midVal < value) fromIndex = mid + 1
            else return mid
        }

        return -(fromIndex + 1)
    }

    /**
     * Get the integer at the given index.
     *
     * @param index The index.
     * @return An integer.
     */
    fun get(index: Int): Int {
        if (d_bitsPerElem == 0) return 0

        val startIdx = (index * d_bitsPerElem) / INT_SIZE
        val startBit = (index * d_bitsPerElem) % INT_SIZE

        var result = (d_data[startIdx] ushr startBit) and MASK!![d_bitsPerElem]

        if ((startBit + d_bitsPerElem) > INT_SIZE) {
            val done = INT_SIZE - startBit
            result = result or ((d_data[startIdx + 1] and MASK[d_bitsPerElem - done]) shl done)
        }

        return result
    }

    /**
     * Set the integer at the given index. **Warning:** if you attempt to store an integer that
     * is wider than the width given to the constructor [.CompactIntArray], the integer
     * is truncated.
     *
     * @param index The index.
     * @param value The value to store.
     */
    fun set(index: Int, value: Int) {
        if (d_bitsPerElem == 0) return

        val startIdx = (index * d_bitsPerElem) / INT_SIZE
        val startBit = (index * d_bitsPerElem) % INT_SIZE

        // Clear data
        d_data[startIdx] = d_data[startIdx] and (MASK!![d_bitsPerElem] shl startBit).inv()

        // And set.
        d_data[startIdx] = d_data[startIdx] or (value shl startBit)

        // If the integer didn't have enough bits available, write the rest in the next integer.
        if ((startBit + d_bitsPerElem) > INT_SIZE) {
            val done = INT_SIZE - startBit
            d_data[startIdx + 1] = d_data[startIdx + 1] and MASK[d_bitsPerElem - done].inv()
            d_data[startIdx + 1] = d_data[startIdx + 1] or (value ushr done)
        }
    }

    /**
     * Get the size of the array.
     *
     * @return The size.
     */
    fun size(): Int {
        return d_size
    }

    companion object {
        private const val serialVersionUID = 1L
        private const val INT_SIZE = 32
        private val MASK: IntArray? = intArrayOf(
            0x0, 0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f, 0xff, 0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff,
            0x3fff, 0x7fff, 0xffff, 0x1ffff, 0x3ffff, 0x7ffff, 0xfffff, 0x1fffff, 0x3fffff, 0x7fffff, 0xffffff,
            0x1ffffff, 0x3ffffff, 0x7ffffff, 0xfffffff, 0x1fffffff, 0x3fffffff, 0x7fffffff, -0x1
        )

        fun width(n: Int): Int {
            return INT_SIZE - n.countLeadingZeros()
        }
    }
}
